#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <mpi.h>
#include <omp.h>
#include "fun_group.h"
#include "bs_fun.h"

int main() {
	int local_n;	// 各个进程中数组的大小
	int* A, * B;	// A为进程中保存的数据，B为进程通信中获得的数据
	int comm_sz, my_rank;
	double all_start_time, all_end_time, end_time, start_time;
	int DataSize = 1e5;

	MPI_Init(NULL, NULL);
	// 获得进程数和当前进程的编号
	MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
	MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
 
	// 计算每个进程应当获得的数据量，动态开辟空间 
	local_n = DataSize / comm_sz;
	A = (int *)malloc(local_n*sizeof(int));
	B = (int *)malloc(local_n*sizeof(int));
	// 随机产生数据并分发至各个进程
	if (my_rank == 0){
		all_start_time = omp_get_wtime();
	}
	Get_Input(A, local_n, my_rank, DataSize);
 
	// 先有序化本地数据
	serial_BubbleSort(A, local_n);
 
	// 定理：如果p个进程运行奇偶排序算法，那么p个阶段后，输入列表有序
	for (int i = 0; i < comm_sz; i++) {
		// 获得本次交换数据的进程号
		int partner = Get_Partner(my_rank, i);
		// 如果本次数据交换的进程号有效
		if (partner != -1 && partner != comm_sz) {
			// 与对方进程交换数据
			MPI_Sendrecv(A, local_n, MPI_INT, partner, 0, B, local_n, MPI_INT, partner, 0, MPI_COMM_WORLD, MPI_STATUSES_IGNORE);
			// 如果本进程号大于目标进程，就应该取值较大的部分
			if (my_rank > partner) {
				Merge_High(A, B, local_n);
			}
			// 否则应该取值较小的部分
			else {
				Merge_Low(A, B, local_n);
			}
		}
	}
 
	all_end_time = omp_get_wtime();
	MPI_Finalize();

	if (my_rank == 0){
		printf("排序后的有序数组为 :\n");
		for (int i = 0; i < 100; ++i){
			printf("%d ", A[i]);
		}
		puts("");

		// 计算串行时间
		int data[DataSize];
		CreateData(data, DataSize);
		start_time = omp_get_wtime();
		serial_BubbleSort(data, DataSize);
		end_time = omp_get_wtime();
		
		char sort_name[] = "mpi_bubblle";
		char filepath[] = "result_mpi_bubble.txt";
		put_time_info(filepath, sort_name, DataSize, comm_sz, all_start_time, all_end_time, start_time, end_time);
	}

	return 0;
}
